﻿
using System.Collections.Generic;

public static class Helpers
{
    public static int[] Triangulate(UnityEngine.Vector2[] points)
    {
        List<int> indices = new List<int>();

        int n = points.Length;
        if (n < 3)
        {
            return indices.ToArray();
        }

        int[] triangles = new int[n];
        if (Helpers.Area(points) > 0)
        {
            for (int v = 0; v < n; v++)
            {
                triangles[v] = v;
            }
        }
        else
        {
            for (int v = 0; v < n; v++)
            {
                triangles[v] = (n - 1) - v;
            }
        }

        int nv = n;
        int count = 2 * nv;
        for (int m = 0, v = nv - 1; nv > 2;)
        {
            if ((count--) <= 0)
            {
                return indices.ToArray();
            }

            int u = v;
            if (nv <= u)
            {
                u = 0;
            }

            v = u + 1;
            if (nv <= v)
            {
                v = 0;
            }

            int w = v + 1;
            if (nv <= w)
            {
                w = 0;
            }

            if (Helpers.Snip(u, v, w, nv, triangles, points))
            {
                int a, b, c, s, t;

                a = triangles[u];
                b = triangles[v];
                c = triangles[w];
                indices.Add(a);
                indices.Add(b);
                indices.Add(c);
                m++;

                for (s = v, t = v + 1; t < nv; s++, t++)
                {
                    triangles[s] = triangles[t];
                }

                nv--;
                count = 2 * nv;
            }
        }

        indices.Reverse();
        return indices.ToArray();
    }

    public static int[] Triangulate(UnityEngine.Vector3[] points)
    {
        List<int> indices = new List<int>();

        int n = points.Length;
        if (n < 3)
        {
            return indices.ToArray();
        }

        int[] triangles = new int[n];
        if (Helpers.Area(points) > 0)
        {
            for (int v = 0; v < n; v++)
            {
                triangles[v] = v;
            }
        }
        else
        {
            for (int v = 0; v < n; v++)
            {
                triangles[v] = (n - 1) - v;
            }
        }

        int nv = n;
        int count = 2 * nv;
        for (int m = 0, v = nv - 1; nv > 2; )
        {
            if ((count--) <= 0)
            {
                return indices.ToArray();
            }

            int u = v;
            if (nv <= u)
            {
                u = 0;
            }

            v = u + 1;
            if (nv <= v)
            {
                v = 0;
            }

            int w = v + 1;
            if (nv <= w)
            {
                w = 0;
            }

            if (Helpers.Snip(u, v, w, nv, triangles, points))
            {
                int a, b, c, s, t;

                a = triangles[u];
                b = triangles[v];
                c = triangles[w];
                indices.Add(a);
                indices.Add(b);
                indices.Add(c);
                m++;

                for (s = v, t = v + 1; t < nv; s++, t++)
                {
                    triangles[s] = triangles[t];
                }

                nv--;
                count = 2 * nv;
            }
        }

        indices.Reverse();
        return indices.ToArray();
    }

    private static float Area(UnityEngine.Vector2[] points)
    {
        float area = 0.0f;
        for (int p = points.Length - 1, q = 0; q < points.Length; p = q++)
        {
            UnityEngine.Vector2 pval = points[p];
            UnityEngine.Vector2 qval = points[q];

            area += (pval.x * qval.y) - (qval.x * pval.y);
        }

        return area * 0.5f;
    }

    private static float Area(UnityEngine.Vector3[] points)
    {
        float area = 0.0f;
        for (int p = points.Length - 1, q = 0; q < points.Length; p = q++)
        {
            UnityEngine.Vector2 pval = points[p];
            UnityEngine.Vector2 qval = points[q];

            area += (pval.x * qval.y) - (qval.x * pval.y);
        }

        return area * 0.5f;
    }

    private static bool InsideTriangle(UnityEngine.Vector2 pointA, UnityEngine.Vector2 pointB, UnityEngine.Vector2 pointC, UnityEngine.Vector2 pointP)
    {
        float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
        float cCROSSap, bCROSScp, aCROSSbp;

        ax = pointC.x - pointB.x;
        ay = pointC.y - pointB.y;

        bx = pointA.x - pointC.x;
        by = pointA.y - pointC.y;

        cx = pointB.x - pointA.x;
        cy = pointB.y - pointA.y;

        apx = pointP.x - pointA.x;
        apy = pointP.y - pointA.y;

        bpx = pointP.x - pointB.x;
        bpy = pointP.y - pointB.y;

        cpx = pointP.x - pointC.x;
        cpy = pointP.y - pointC.y;

        aCROSSbp = (ax * bpy) - (ay * bpx);
        cCROSSap = (cx * apy) - (cy * apx);
        bCROSScp = (bx * cpy) - (by * cpx);

        return (aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f);
    }

    private static bool InsideTriangle(UnityEngine.Vector3 pointA, UnityEngine.Vector3 pointB, UnityEngine.Vector3 pointC, UnityEngine.Vector3 pointP)
    {
        float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
        float cCROSSap, bCROSScp, aCROSSbp;

        ax = pointC.x - pointB.x;
        ay = pointC.y - pointB.y;

        bx = pointA.x - pointC.x;
        by = pointA.y - pointC.y;

        cx = pointB.x - pointA.x;
        cy = pointB.y - pointA.y;

        apx = pointP.x - pointA.x;
        apy = pointP.y - pointA.y;

        bpx = pointP.x - pointB.x;
        bpy = pointP.y - pointB.y;

        cpx = pointP.x - pointC.x;
        cpy = pointP.y - pointC.y;

        aCROSSbp = (ax * bpy) - (ay * bpx);
        cCROSSap = (cx * apy) - (cy * apx);
        bCROSScp = (bx * cpy) - (by * cpx);

        return (aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f);
    }

    private static bool Snip(int u, int v, int w, int n, int[] triangles, UnityEngine.Vector2[] points)
    {
        int p;
        UnityEngine.Vector2 sideA = points[triangles[u]];
        UnityEngine.Vector2 sideB = points[triangles[v]];
        UnityEngine.Vector2 sideC = points[triangles[w]];

        if (UnityEngine.Mathf.Epsilon > (((sideB.x - sideA.x) * (sideC.y - sideA.y)) - ((sideB.y - sideA.y) * (sideC.x - sideA.x))))
        {
            return false;
        }

        for (p = 0; p < n; p++)
        {
            if ((p == u) || (p == v) || (p == w))
            {
                continue;
            }

            UnityEngine.Vector2 point = points[triangles[p]];
            if (Helpers.InsideTriangle(sideA, sideB, sideC, point))
            {
                return false;
            }
        }

        return true;
    }

    private static bool Snip(int u, int v, int w, int n, int[] triangles, UnityEngine.Vector3[] points)
    {
        int p;
        UnityEngine.Vector3 sideA = points[triangles[u]];
        UnityEngine.Vector3 sideB = points[triangles[v]];
        UnityEngine.Vector3 sideC = points[triangles[w]];

        if (UnityEngine.Mathf.Epsilon > (((sideB.x - sideA.x) * (sideC.y - sideA.y)) - ((sideB.y - sideA.y) * (sideC.x - sideA.x))))
        {
            return false;
        }

        for (p = 0; p < n; p++)
        {
            if ((p == u) || (p == v) || (p == w))
            {
                continue;
            }

            UnityEngine.Vector3 point = points[triangles[p]];
            if (Helpers.InsideTriangle(sideA, sideB, sideC, point))
            {
                return false;
            }
        }

        return true;
    }
}